| 翻訳と辞書 |
| Mutilated chessboard problem ： ウィキペディア英語版 |
Mutilated chessboard problem
The mutilated chessboard problem is a tiling puzzle proposed by philosopher Max Black in his book ''Critical Thinking'' (1946). It was later discussed by Solomon W. Golomb (1954), or by Martin Gardner in his ''Scientific American'' column "Mathematical Games." The problem is as follows:
Suppose a standard 8x8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2x1 so as to cover all of these squares?
Most considerations of this problem in literature provide solutions "in the conceptual sense" without proofs. John McCarthy proposed it as a hard problem for automated proof systems. In fact, its solution using the resolution system of inference is exponentially hard.〔.〕
== Solution ==
The puzzle is impossible to complete. A domino placed on the chessboard will always cover one white square and one black square. Therefore, a collection of dominoes placed on the board will cover an equal numbers of squares of each colour. If the two white corners are removed from the board then 30 white squares and 32 black squares remain to be covered by dominoes, so this is impossible. If the two black corners are removed instead, then 32 white squares and 30 black squares remain, so it is again impossible.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Mutilated chessboard problem」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|